package com.fengye.algorithms.leecode.graph;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @Author fengye
 * @Date 2023/4/27 8:35
 **/
public class AllPathsFromSourceToTarget797 {

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        Deque<Integer> queue = new ArrayDeque<>();
        List<List<Integer>> result = new ArrayList<>();
        queue.offer(0);
        dfs(graph, 0, graph.length - 1, result, queue);
        return result;
    }

    public void dfs(int[][] graph, int cur, int n, List<List<Integer>> result, Deque<Integer> queue) {
        // 到达最后，加入结果
        if(cur == n) {
            result.add(new ArrayList<>(queue));
            return;
        }

        for(int col : graph[cur]) {
            queue.offer(col);
            dfs(graph, col, n, result, queue);
            queue.poll();
        }
    }
}
